﻿#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

/*****************第九章.函数递归*****************/
/****1. 递归是什么？****/

//main函数也是函数，main函数调用mian函数就是递归
//最终会崩溃
//这是一种错误递归
//int main()
//{
//	printf("hehe\n");
//	main();
//	return 0;
//}

//举例1：求n的阶乘

//int fac(int n)
//{
//	if (n >= 1)
//		return fac(n - 1) * n;
//	else
//		return 1;
//}

//int fac(int n)
//{
//	int i = 0;
//	int ret = 1;
//	for (i = 1;i <= n; i++)
//	{
//		ret *= i;
//	}
//	return ret;
//
//}

//int main()
//{
//	int n = 0;
//	scanf("%d",&n);
//	int r = fac(n);
//	printf("%d ",r);
//	return 0;
//}

//举例2：顺序打印⼀个整数的每⼀位
//void Print(int n)
//{
//	if (n > 9)
//	{
//		Print(n/10);
//	}
//	printf("%d ",n % 10);
//}
//int main()
//{
//	int n = 0;
//	scanf("%d",&n);
//
//	//while (n)
//	//{
//	//	printf("%d ", n % 10);
//	//	n = n / 10;
//	//}
//	Print(n);//可以将n按顺序打印
//	return 0;
//}

/**************2. 递归与迭代************/
//迭代的⽅式（通常就是循环的⽅式）
//求n的阶乘
//int fac(int n)
//{
//	int i = 0;
//	int ret = 1;
//	for (i = 1;i <= n; i++)
//	{
//		ret *= i;
//	}
//	return ret;
//
//}

//举例3：求第n个斐波那契数
//int Fib(int n)
//{
//	if (n <= 2)
//		return 1;
//	else
//		return Fib(n - 1) + Fib(n - 2);
//}

int Fib(int n)
{
	int a = 1;
	int b = 1;
	int c = 1;
	while (n>2)
	{
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
}
int main()
{
	int n = 0;
	scanf("%d",&n);
	int r = Fib(n);
	printf("%d\n",r);
	return 0;
}